import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class Code_98 {

    public boolean isValidBST(TreeNode root) {
        //定义两个边界，这时这道题的核心，我们在一次次的递归中
        //也在不断地为每个节点缩小上下限的范围，一旦超出便是false
        Long max = Long.MAX_VALUE;
        Long min = Long.MIN_VALUE;
        return valid(root, max, min);
    }
    //
    private boolean valid(TreeNode node, long max, long min){
        if(node == null){
            return true;
        }
        //开始递归
        /**
         这里解释一下当节点为node的时候，
         左节点永远不会大于node，所以左节点的范围最大值便是node.val
         右节点永远不会小于node，所以有节点的最小值范围是node.val
         但是这里还有一点要注意，但我们的node.left的right节点如果存在
         那么node.left.right这个节点虽然要大于node.left，也就是下线是node.left，
         但是上限依旧受到node的父节点的限制node.left.right范围为(node.val, node父节点.val)
         ，由此可推到node的right节点及其子节点的范围，便可得到该递归
         */
        boolean left = valid(node.left, node.val ,min);
        boolean right = valid(node.right, max , node.val);
        //当前节点大于最大值或者小于最小值，root的时候是和一个初始值比较所以root必定为true
        //后续递归
        if( node.val >= max || node.val <= min){
            return false;
        }
        return left && right;
    }

    /**
     * 方法2: 如果一个二叉树的中序遍历结果是升序的，则此二叉树为二叉搜索树
     */
    List<Integer> list =new ArrayList<>();
    public boolean isValidBST2(TreeNode root) {

        return inorderTraversal(root);
    }

    long pre = Long.MIN_VALUE; // 记录上一个节点的值，初始值为Long的最小值
    public boolean inorderTraversal(TreeNode node) {
        if (node == null){
            return true;
        }
        boolean l = inorderTraversal(node.left);
        if(node.val <= pre) { // 比较当前节点和上个节点的值
            return false;
        }
        pre = node.val; //指向当前节点
        boolean r = inorderTraversal(node.right);
        return l && r;
    }
}
